package top.minuy.structure.hash;

import top.minuy.structure.map.AVLTreeMap;

/**
 * @author Minuy
 * @time 12:34
 * @date 2021/11/9
 */
public class AVLTreeHashTable<K extends Comparable<K>,V> implements HashTable<K,V> {

    /**
     * 散列表建议容量
     * 来源：http://planetmath.org/goodhashtableprimes
     * lwr   upr   % err      prime
     * 2^5   2^6   10.416667  53
     * 2^6   2^7   1.041667   97
     * 2^7   2^8   0.520833   193
     * 2^8   2^9   1.302083   389
     * 2^9   2^10  0.130208   769
     * 2^10  2^11  0.455729   1543
     * 2^11  2^12  0.227865   3079
     * 2^12  2^13  0.113932   6151
     * 2^13  2^14  0.008138   12289
     * 2^14  2^15  0.069173   24593
     * 2^15  2^16  0.010173   49157
     * 2^16  2^17  0.013224   98317
     * 2^17  2^18  0.002543   196613
     * 2^18  2^19  0.006358   393241
     * 2^19  2^20  0.000127   786433
     * 2^20  2^21  0.000318   1572869
     * 2^21  2^22  0.000350   3145739
     * 2^22  2^23  0.000207   6291469
     * 2^23  2^24  0.000040   12582917
     * 2^24  2^25  0.000075   25165843
     * 2^25  2^26  0.000010   50331653
     * 2^26  2^27  0.000023   100663319
     * 2^27  2^28  0.000009   201326611
     * 2^28  2^29  0.000001   402653189
     * 2^29  2^30  0.000011   805306457
     * 2^30  2^31  0.000000   1610612741
     */
    private final static int[] capacities = {
            //1, 2, 3, 4, 5
            53, 97, 193, 389, 769, 1543,
            3079, 6151, 12289, 24593, 49157, 98317,
            196613, 393241, 786433, 1572869, 3145739, 6291469,
            12582917, 25165843, 50331653, 100663319, 201326611, 402653189,
            805306457, 1610612741
    };
    // 平均冲突值上界
    private final static int upperTol = 10;
    // 平均冲突值下界
    private final static int lowerTol = 2;

    // 当前主容量索引
    private int capacityIndex;
    // 当前大小
    private int size;
    // 保存数据的数组
    private AVLTreeMap<K, V>[] table;

    public AVLTreeHashTable() {
        capacityIndex = 0;
        size = 0;
        table = new AVLTreeMap[capacities[capacityIndex]];

        for (int i = 0; i < table.length; i++) {
            table[i] = new AVLTreeMap<>();
        }
    }

    /**
     * 添加元素到散列表中
     *
     * @param key 元素的键
     * @param val 元素的值
     */
    @Override
    public void add(K key, V val) {
        int hash = getHash(key);
        AVLTreeMap<K, V> map = table[hash];

        if (map.contains(key)) {
            map.set(key, val);
        } else {
            map.add(key, val);
            size++;

            if ((capacityIndex < (capacities.length - 1)) && ((size / capacities[capacityIndex]) > upperTol)) {
                capacityIndex++;
                resize(capacities[capacityIndex]);
            }
        }
    }

    /**
     * 从散列表中删除元素
     *
     * @param key 要删除元素的键
     * @return 被删除的元素值
     */
    @Override
    public V remove(K key) {
        int hash = getHash(key);
        AVLTreeMap<K, V> map = table[hash];

        V val = null;
        if (map.contains(key)) {
            val = map.remove(key);
            size--;

            if ((capacityIndex > 0) && ((size / capacities[capacityIndex]) < lowerTol)) {
                capacityIndex--;
                resize(capacities[capacityIndex]);
            }
        }

        return val;
    }

    /**
     * 从散列表中获取值
     *
     * @param key 要获取的元素的键
     * @return 被获取的元素的值
     */
    @Override
    public V get(K key) {
        int hash = getHash(key);
        return table[hash].get(key);
    }

    /**
     * 验证元素是否存在散列表中
     *
     * @param key 要验证元素的键
     * @return 是否存在散列表中
     */
    @Override
    public boolean contains(K key) {
        int hash = getHash(key);
        return table[hash].contains(key);
    }

    /**
     * 修改散列表中的元素值
     *
     * @param key 要修改的元素的键
     * @param val 元素被修改之后的值
     */
    @Override
    public void set(K key, V val) {
        int hash = getHash(key);
        AVLTreeMap<K, V> map = table[hash];

        if (map.contains(key)) {
            map.set(key, val);
        } else {
            throw new IllegalArgumentException("Set failed. " + key + " is not contains.");
        }
    }

    /**
     * 获取当前散列表存储元素的个数
     *
     * @return 当前散列表存储元素的个数
     */
    @Override
    public int getSize() {
        return size;
    }

    /**
     * 返回当前散列表是否为空
     *
     * @return 散列表是否为空
     */
    @Override
    public boolean isEmpty() {
        return size == 0;
    }

    /**
     * 哈希函数，获取元素的键的哈希值
     *
     * @param key 要计算的键
     * @return 被计算的键的哈希值
     */
    private int getHash(K key) {

        // System.out.println((key.hashCode() & 0x7fffffff) % capacities[capacityIndex]);
        // % 的优先级大于 & 的优先级
        return (key.hashCode() & 0x7fffffff) % capacities[capacityIndex];
    }

    /**
     * 重新分配散列表大小
     *
     * @param capacity 新的散列表大小
     */
    private void resize(int capacity) {
        // System.out.println("resize : " + capacity + " size : " + size);

        AVLTreeMap<K, V>[] newTable;
        newTable = new AVLTreeMap[capacity];
        for (int i = 0; i < newTable.length; i++) {
            newTable[i] = new AVLTreeMap<>();
        }

        Object[] keyArray;
        for (int i = 0; i < table.length; i++) {
            AVLTreeMap<K, V> map = table[i];
            keyArray = map.getKeyArray();
            for (int j = 0; j < keyArray.length; j++) {
                // System.out.println("["+j+"]"+keyArray[j] + " ");
                K key = (K) keyArray[j];
                int hash = getHash(key);
                newTable[hash].add(key, map.get(key));
            }
//            System.out.println();
//            System.out.println("index : " + i);
        }

        table = newTable;
    }
}
